#include <stdio.h>
#define  N  10

/* https://c.biancheng.net/view/quick-sort.html */
/* https://blog.csdn.net/qz652219228/article/details/120070756 */

int partition(int data[], int low, int high) {
    /* 用data[low]作为枢轴元素pivot进行划分 */
    /* 使得data[low..i-1]均不大于pivot, data[i+1..high]均不小于pivot */
    int i, j;
    int pivot;
    pivot = data[low];
    i = low;
    j = high;
    /* 从数组的两端交替地向中间扫描 */
    while (i < j)
    {
        /* code */
        while(i < j && data[j] >= pivot) {
            j--;
        }
        /* 比枢轴元素小者往前移 */
        data[i] = data[j];
        while(i < j && data[i] <= pivot) {
            i++;
        }
        /* 比枢轴元素大者往后移 */
        data[j] = data[i];
    }
    data[i] = pivot;
    return i;
}

void quickSort(int data[], int low, int high) {
    /* 用快速排序方法对数组元素data[low..high]作非递减排序 */
    if(low < high) {
        /* 进行划分 */
        int loc = partition(data, low, high);
        /* 对前半区进行快速排序 */
        quickSort(data, low, loc-1);
        /* 对后半区进行快速排序 */
        quickSort(data, loc+1, high);
    }
}

int main(int argc, char * argv[]) {
    int i = 0; 
    int arr[N] = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31};
    /* 对arr数组中所有元素进行快速排序 */
    quickSort(arr, 0, N-1);
    for(i = 0; i < N; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}